#-*-coding:utf-8-*-
#author:fanerlei
#date:2021.8.24
# 树的几种变量方式
import  time
# 前序
def _preOrder(root, tmpList):
	if not root:
		return
	tmpList.append(root.val)
	if root.left:
		_preOrder(root.left, tmpList)
	if root.right:
		_preOrder(root.right, tmpList)

def preOrder(root):
	tmpList = []
	tmpNodeList = [root]
	while tmpNodeList:
		node = tmpNodeList.pop()
		tmpList.append(node.val)
		if node.right:
			tmpNodeList.append(node.right)
		if node.left:
			tmpNodeList.append(node.left)

	# self._preOrder(root,tmpList)
	return tmpList

# 中序

def _inOder( root, tmpList):
	if not root:
		return tmpList
	if root.left:
		_inOder(root.left, tmpList)
	tmpList.append(root.val)
	if root.right:
		_inOder(root.right, tmpList)


def inOrder(root):
	tmpList = []
	tmpNodeList = []
	# self._inOder(root,tmpList)
	while root or tmpNodeList:
		while root:
			tmpNodeList.append(root)
			root = root.left
		if tmpNodeList:
			root = tmpNodeList.pop()
			tmpList.append(root.val)
			root = root.right

	return tmpList

# 后序

def _postOrder( root, tmpList):
	if not root:
		return
	if root.left:
		_postOrder(root.left, tmpList)
	if root.right:
		_postOrder(root.right, tmpList)
	tmpList.append(root.val)

# 广度优先遍历
def levelOrder(self, root):
	tmpList = []
	if not root:
		return tmpList

	queue = [root]
	while queue:
		res_lever = []
		for i in range(len(queue)):
			cur_node = queue.pop(0)
			res_lever.append(cur_node.val)
			if cur_node.left:
				queue.append(cur_node.left)
			if cur_node.right:
				queue.append(cur_node.right)
		tmpList.append(res_lever)
	return tmpList


def rotate( nums, k):
	"""
	:type nums: List[int]
	:type k: int
	:rtype: None Do not return anything, modify nums in-place instead.
	"""
	tmpList = []
	numCount = len(nums)
	for idx in xrange(0, k + 1):
		tmpList.append(nums[idx])

	nums = nums[k + 1:numCount]
	nums.extend(tmpList)
	nums [:] = nums
	print  nums


def reverse( x):
	"""
	:type x: int
	:rtype: int
	"""
	op = 1 if x > 0 else -1
	ret = str(abs(x))
	retList = [s for s in ret]
	if len(ret) == 1:
		return x

	reverseString(retList)
	retNum = int("".join(retList)) * op
	if retNum > pow(2, 31)-1 or retNum < pow(2, -31):
		return 0
	return retNum


def reverseString( s):
	i, j = 0, len(s) - 1

	while (i < j):
		s[i], s[j] = s[j], s[i]
		i += 1
		j -= 1


def getCommonStr(str1, str2):
	print str1,str2
	if not str1 or not str2:
		return 0
	i = j = 0

	if len(str1) > len(str2):
		tStr = str1
		sStr = str2
	else:
		tStr = str2
		sStr = str1
	maxLenCount = 0
	maxStringCount = len(tStr)
	sStrCount = len(sStr)
	startIdx = -1
	while (i < maxStringCount and j < sStrCount):
		print j,i
		if tStr[i] == sStr[j]:
			if startIdx < 0:
				startIdx = i
			maxLenCount = max(maxLenCount, i - startIdx+1)
			j += 1
			j = j if j < sStrCount else sStrCount-1
		else:
			j = 0
			startIdx = -1
		i += 1
		#i = i if i < maxStringCount else maxStringCount-1
	print "end while loop"
	print i, j, startIdx
	print maxLenCount
	return maxLenCount
# def testFunc():
# 	return 2
#
# def testFunc2():
# 	print "get nothing "
#
# def testFunc1(param):
# 	print param
if __name__ == '__main__':
	pass
	# testFunc1(testFunc)
	# testFunc1(testFunc())
	# testFunc(testFunc2())
	enumerate
	tmpNum = [1,2,3,4,5,6,7]
	rotate(tmpNum,3)
	print  tmpNum
	print -pow(2,31)
	print dir(dict)
	print " ass   ".index("ss")
	print 2 & 1
	print  time.time()
	print getCommonStr("werasdfaswer","asdfas")
	print time.time()
	num = 132
	isFirst = False
	count = 0
	# while num > 0:
	# 	print num,count
	# 	if num & 1 == 1:
	# 		if not isFirst:
	# 			isFirst = True
	# 			count = 1
	# 		else:
	# 			count += 1
	# 	else:
	# 		isFirst = False
	# 	num = num >> 1
	while num > 0:
		print num, count
		if num & 1 == 1:
			if not isFirst:
				isFirst = True
				count = 1
			else:
				count += 1
		else:
			isFirst = False
		num = num >> 1
	print count
	print int("-123")